package ink.lovejinhu.leetcode;

import java.util.HashMap;

/**
 * @author jinhu
 * created 2021-07-04 9:59
 */
public class Solution_0169 {
    /**
     * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素
     * 摩尔投票法
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> res = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (res.containsKey(nums[i])) {
                Integer integer = res.get(nums[i]);
                if ((integer + 1) >= (nums.length + 1) >> 1) return nums[i];
                res.put(nums[i], integer + 1);
                continue;
            }
            res.put(nums[i], 1);
        }
        return nums[0];
    }

    public static void main(String[] args) {
        Solution_0169 solution_0169 = new Solution_0169();
       // int[] test = {3, 2, 3};
        int[] test = {2,2,1,1,1,2,2};
        solution_0169.majorityElement(test);
    }

}
